Let $G$ be a graph such that each edge has its list of available colors, andassume that each list is a subset of the common set consisting of $k$ colors.Suppose that we are given two list edge-colorings $f_0$ and $f_r$ of $G$, andasked whether there exists a sequence of list edge-colorings of $G$ between$f_0$ and $f_r$ such that each list edge-coloring can be obtained from theprevious one by changing a color assignment of exactly one edge. This problemis known to be PSPACE-complete for every integer $k \ge 6$ and planar graphs ofmaximum degree three, but any complexity hardness was unknown for the non-listvariant. In this paper, we first improve the known result by proving that, forevery integer $k \ge 4$, the problem remains PSPACE-complete even if an inputgraph is planar, bounded bandwidth, and of maximum degree three. We then givethe first complexity hardness result for the non-list variant: for everyinteger $k \ge 5$, we prove that the non-list variant is PSPACE-complete evenif an input graph is planar, of bandwidth linear in $k$, and of maximum degree$k$.
展开▼
机译:假设$ G $是一个图形,使得每个边缘都有其可用颜色的列表,并假设每个列表都是由$ k $颜色组成的公共集的子集。假设我们给了两个列表边缘颜色$ f_0 $和$ g_ $的$ f_r $,并询问在$ f_0 $和$ f_r $之间是否存在$ G $的列表边缘着色序列,以便可以通过更改颜色分配为来从上一个获得每个列表边缘着色恰好一个边缘。对于每个整数$ k \ ge 6 $和最大度数为3的平面图,已知此问题都是PSPACE完全的,但对于非列表变量,其复杂度硬度是未知的。在本文中,我们首先通过证明对于每个整数$ k \ ge 4 $,即使输入图是平面的,有界带宽的且最大度数为3,问题仍然保持PSPACE完全,从而改善了已知结果。然后,我们给出非列表变量的第一个复杂度硬度结果:对于每个整数$ k \ ge 5 $,我们证明即使输入图是平面的,带宽线性单位为$ k $,该非列表变量也是PSPACE-complete,最高学历为$ k $。
展开▼